package com.example.demo.leetcode;

/**
 * 链接: <a href='https://leetcode.cn/problems/valid-sudoku/description/?envType=study-plan-v2&envId=top-interview-150'>https://leetcode.cn/problems/valid-sudoku/description/?envType=study-plan-v2&envId=top-interview-150</a><br>
 * <p>
 * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。<br>
 * <p>
 * 1. 数字 1-9 在每一行只能出现一次。<br>
 * 2. 数字 1-9 在每一列只能出现一次。<br>
 * 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）<br>
 * <p>
 * 注意：
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。<br>
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。<br>
 * 空白格用 '.' 表示。<br>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/23 16:21
 */
public class _36_有效的数独 {

    public static void main(String[] args) {

        char[][] board2 = {
                {'.', '.', '.', '.', '5', '.', '.', '1', '.'},
                {'.', '4', '.', '3', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '3', '.', '.', '1'},
                {'8', '.', '.', '.', '.', '.', '.', '2', '.'},
                {'.', '.', '2', '.', '7', '.', '.', '.', '.'},
                {'.', '1', '5', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '2', '.', '.', '.'},
                {'.', '2', '.', '9', '.', '.', '.', '.', '.'},
                {'.', '.', '4', '.', '.', '.', '.', '.', '.'}};

        char[][] board1 = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}
                , {'6', '.', '.', '1', '9', '5', '.', '.', '.'}
                , {'.', '9', '8', '.', '.', '.', '.', '6', '.'}
                , {'8', '.', '.', '.', '6', '.', '.', '.', '3'}
                , {'4', '.', '.', '8', '.', '3', '.', '.', '1'}
                , {'7', '.', '.', '.', '2', '.', '.', '.', '6'}
                , {'.', '6', '.', '.', '.', '.', '2', '8', '.'}
                , {'.', '.', '.', '4', '1', '9', '.', '.', '5'}
                , {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

        char[][] board = {{'8', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

        boolean validSudoku = new Solution().isValidSudoku(board2);
        System.out.println(validSudoku);

    }

    public static class Solution {

        /**
         * 官网题解：三维数组，太过于难以理解了。
         * 有三维数组来表示区域
         * 时间复杂度O(1)
         * 空间复杂度O(1)
         */
        public boolean isValidSudoku(char[][] board) {
            //行
            int[][] rows = new int[9][9];
            //列
            int[][] columns = new int[9][9];
            //区域
            int[][][] subboxes = new int[3][3][9];

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char c = board[i][j];
                    if (c != '.') {
                        int index = c - '0' - 1;
                        rows[i][index]++;
                        columns[j][index]++;
                        subboxes[i / 3][j / 3][index]++;
                        if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }


        /**
         * 全部用二维数组的方式，相对三维数组好理解多了。
         * 用二维数组来表示区域：区域下标：int idx = i / 3 * 3 + j / 3;
         *
         * <p>
         * 时间复杂度O(1)
         * 空间复杂度O(1)
         */
        public boolean isValidSudoku1(char[][] board) {
            //行
            boolean[][] row = new boolean[10][10];
            //列
            boolean[][] col = new boolean[10][10];
            //区域
            boolean[][] area = new boolean[10][10];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    int c = board[i][j];
                    if (c == '.') {
                        continue;
                    }
                    int u = c - '0';
                    int idx = i / 3 * 3 + j / 3;
                    if (row[i][u] || col[j][u] || area[idx][u]) {
                        return false;
                    }
                    row[i][u] = col[j][u] = area[idx][u] = true;
                }
            }
            return true;
        }

        /**
         * 进阶：用位运算来进行表示 <br>
         * 位运算占用更少的内存和时间。<br>
         * <p>
         * 二进制 用某一位的1代表这个数字出现过，因为题目存储的数字范围是1~9，所以我们需要9个位来标记数字，而int 的 二进制 是32位，所以足以存储。<br>
         *
         * <p>
         * 时间复杂度O(1)
         * 空间复杂度O(1)
         */
        public boolean isValidSudoku2(char[][] board) {
            // java数组初始化默认为0
            int[] row = new int[9]; //row[0] 表示第一行的数据
            int[] col = new int[9];
            int[] v = new int[9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    //移位到当前数字存储位
                    //1的二进制位为000 000 001
                    //当board[i][j]的值为5时，左移五位就变成了 000 100 000
                    //用此来表示
                    int num = 1 << (board[i][j] - '0');

                    int b = (i / 3) * 3 + j / 3;
                    // &运算，同为1才为1。
                    //想要不重复，位置上的数据就不能相同，&运算之后肯定为0
                    if ((row[i] & num) != 0 || (col[j] & num) != 0 || (v[b] & num) != 0) {
                        return false;
                    }
                    //或运算：只有有一个为1，就为1
                    //把位置信息写入数组中。
                    row[i] |= num;
                    col[j] |= num;
                    v[b] |= num;
                }
            }
            return true;
        }
    }
}
